3.2 The Map Method

It was cited in the previous discussions that a Boolean function can be described both by a truth table and by an algebraic equation. Each form has its own advantages.

A truth table shows specific value for each possible input combination. But it is not closely related to a corresponding logic circuitry. From the truth table, several forms of the logic expression may be obtained.

On the other hand, an algebraic equation representing a Boolean function corresponds closely to a particular logic circuitry. And with the use of Boolean algebra, the equation can be manipulated to arrive to many possible logic circuit designs keeping in mind that the better design is one which is simpler and contains fewer gates.

This section presents another way of describing Boolean function, which renders both the advantages given by truth tables and algebraic equations. It is with the use of a Karnaugh Map.

Karnaugh map or K-map → a graphical or pictorial form of a truth table consisting of a square or rectangular array of adjacent cells.

The Map method provides a simple straightforward procedure for simplifying Boolean expressions.

Part 3.2.1 General Principles on the use of K- Map method:

1. Encircle groups of adjacent 1's or essential prime implicants.

2. Write the expression for each encircled group of 1's.

3. OR the expressions obtained in number 2 and this will produce the complete simplified expression for the Boolean function.

Note: There must be as few groups as possible, but enough to cover all '1' or '0' cells at least once.

Part 3.2.2 Rules in Grouping:

1. Only groups of two, four, eight, and sixteen 1's can be encircled.

2. Encircled groups must be square or rectangular in shape.

3. Groups should be made as large as possible without violating rule number 1.

4. Every "1" on the map must be included in at least one group.

5. A "1" can be included in several groups in order to make the group larger.

6. Loops may wrap around one edge of a map to the opposite edge because squares on opposite edges differ only in one variable.

It must be remembered that two cells of a Karnaugh map are adjacent if their respective addresses differ by more than one digit and under the following conditions.

a) The two cells are physically next to each other in the same row or column;

b) they are at opposite ends off rows or column;

c) they occupy identical position in adjacent maps.

A Boolean function having "n" variables needs Karnaugh map made of 2ⁿ cells; wherein each cell has a corresponding unique address which is specified by row and column.

Table 1. 2-Variable Map

	0	1
0
1

Table 2. 3 Variable Map

	0	1
00
01
11
10

Table 3. 3 Variable Map

	00	01	11	10
0
1

Table 4. 4 Variable Map

	00	01	11	10
00
01
11
10

A K-map contains all information present in a truth table. Consider the following

example.

Table 5. Example Truth Table

Inputs			Output
A	B	C	Y
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Table 6. K-Map for Example Truth Table

A\BC	00	01	11	10
0	0	0	1	1
1	1	1	1	1

There are three variables A, B, and C therefore 2³ = 8 squares in the map. The two rows are labeled 0 and 1, respectively for the complemented and uncomplemented value of A. While the four columns are for the four possible combinations of B and C. Note the order in which they appear 00, 01, 11, and 10.

Each square on the map represents only one unique combination of the input variables. And placed inside these squares are the output values corresponding to the combinations of the variables.

It must be noted that each essential prime implicant is translated into a particular product term. When product term is been found for each essential prime implicant, the products are assembled using an OR function. The result is a SUM-OF-PRODUCTS expression corresponding to the given logic function.

A prime implicant is an implicant that cannot be fully enclosed by a larger implicant on a K-map (Karnaugh Map). A prime implicant encloses a maximum number of 1s and as with non-prime implicant is square or rectangular in shape enclosing a number of '1' is an integer power of

2. See the figure for the difference between prime implicant and non-prime implicants.

Table 7. Comparison between Prime implicant (Purple Box) and non-prime implicant (Green Box)

Part 3.2.2 Proper Ways of Grouping and Writing Expression

Each square on a map represents only one unique combination of the variables, a '1' is placed in the square representing the minterm. Zeroes may be inserted in all the remaining squares but common practice dictates omitting the zeroes.

Table 8. K-Map Example 1 (Green box is C’D’ and Purple box is C)

Therefore, the Boolean expression will be F = C’D’+C.

Table 9. K-Map Example 2 (Green box is BD)

Therefore, the Boolean expression will be F = BD

Table 10. K-Map Example 3 (Green box is B’D’)

Therefore, the Boolean expression will be F = B’D’

Table 11. K-Map Example 4 (Green box is A’B’C’D’, purple box is BD, blue box is AD, orange box is CD, and red box is AB’C )

Therefore, the Boolean expression will be F = A’B’C’D’+BD+AD+CD+AB’C.

Table 12. K-Map Example 4 (Green box is BD’)

Therefore, the Boolean expression will be F = BD’.

Table 13. K-Map Example 5 (Green box is B')

Therefore, the Boolean expression will be F =B’.

Example no.1

Reduce the given equation to a simplified sum-of-products form using K-map method.

Y = A' [B'C + B (D'C + D)] + ABC'D

Solution no. 1

Step 1. Put the equation in a sum-of-products before entering the function on a K-map. Label each term. Thus,

Y = A'B'C + A'BCD' + A'BD + ABC'D

and using X + X' = 1,

Y= A'B'C(D + D) + A'BCD' + ABD (C' +C) + ABC'D

the equation becomes

Y= A'B'CD' + A'B'CD + A'BCD' + A'BC'D + A'BCD + ABC'D

Step 2. The Karnaugh map is now drawn and the minterms are entered into its proper place.

Y=	A'B'CD'	+	A'B'CD	+	A'BCD'	+	A'BC'D	+	A'BCD	+	ABC'D
	0010		0011		0110		0101		0111		1101

Table 14. K-Map for Example no 1(with color corresponding to Boolean Expression)

CD\AB	00	01	11	10
00
01		1	1
11	1	1
10	1	1

Table 15. Final K-Map for Example no 1

Step 3. Formulate the Boolean Expression from each box.

The purple box covers two cells in the K-map:

1. Row CD = 01, Column AB = 01

o This cell represents the minterm where A=0, B=1, C=0, D=1.

2. Row CD = 01, Column AB = 11

o This cell represents the minterm where A=1, B=1, C=0, D=1.

Now, let's look at the variables (A, B, C, D) and see which ones remain constant across these two cells and which ones change.

A	B	C	D
0	1	0	1
1	1	0	1

A: Changes from 0 to 1. (Eliminated)

B: Remains 1. (Contributes B)

C: Remains 0. (Contributes C')

D: Remains 1. (Contributes D)

Since A changes, it is eliminated from the term. The variables B, C, and D remain constant with specific values: B=1, C=0, D=1.

Therefore, the simplified Boolean expression for the purple box is B C' D.

The green box covers four cells in the K-map:

Row CD = 11, Column AB = 00

· This cell represents the minterm where A=0, B=0, C=1, D=1.

Row CD = 10, Column AB = 01

· This cell represents the minterm where A=0, B=1, C=1, D=0.

Now, let's look at the variables (A, B, C, D) and see which ones remain constant across these two cells and which ones change.

A	B	C	D
0	0	1	1
0	1	1	0

A: Remains 0. (Contributes A')

B: Changes from 0 to 1. (Eliminated)

C: Remains 1. (Contributes C)

D: Changes from 1 to 0. (Eliminated)

Since B and D changes, it is eliminated from the term. The variables A, and C remain constant with specific values: A=0, C=1.

Therefore, the simplified Boolean expression for the green box is A'C.

Step 4. Combining the Boolean Expression from each box.

From purple box = BC’D

From green box = A’C

Therefore, the simplified Boolean expression is BC’D+A'C.

Example no. 2

Given the truth table below, obtain the simplified expression for the output F using K-map.

Inputs				Output
w	x	y	z	F
0	0	0	0	0
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	1
0	1	1	0	0
0	1	1	1	1
1	0	0	0	1
1	0	0	1	0
1	0	1	0	1
1	0	1	1	0
1	1	0	0	1
1	1	0	1	0
1	1	1	0	1
1	1	1	1	0

Solution no. 2

Step 1: Create the K-Map from the truth table

Step 2: Create the Boolean expression from the Green and Purple Box.

The green box covers four cells in the K-map:

Now, let's look at the variables (w,x,y,z) and see which ones remain constant across these four cells and which ones change.

w	x	y	z
0	0	0	1
0	1	1	1

w: Remains 0. (Contributes w')

x: Changes from 0 to 1. (Eliminated)

y: Changes from 0 to 1. (Eliminated)

z: Remains 1. (Contributes z)

Therefore, the simplified Boolean expression for the green box is w’z.

The purple box covers four cells in the K-map:

Now, let's look at the variables (w,x,y,z) and see which ones remain constant across these four cells and which ones change.

w	x	y	z
1	1	0	0
1	0	1	0

w: Remains 1. (Contributes w)

x: Changes from 1 to 0. (Eliminated)

y: Changes from 0 to 1. (Eliminated)

z: Remains 0. (Contributes z’)

Therefore, the simplified Boolean expression for the green box is wz’.

Step 3. Combining the Boolean Expression from each box.

From purple box = w’z

From green box = wz’

Therefore, the simplified Boolean expression is F = w’z+wz’.

Example no. 3

Simplify F(x,y,z) = ∑(0,2,5,6)

Solution no. 3

Step 1: Convert F(x,y,z) = ∑(0,2,5,6) to K-Map

This notation means that the function F will output a '1' for the minterms (input combinations) corresponding to the decimal values 0, 2, 5, and 6. For all other minterms, the function output will be '0'.

Convert Decimal Minterms to 3-bit Binary:

Since there are three variables (x, y, z), each minterm will be represented by a 3-bit binary string. It's helpful to list these conversions clearly:

0	2	5	6
000	010	101	110

Populate the 3-Variable Karnaugh Map:

A 3-variable K-map has 2³=8 cells. Each cell corresponds to a unique minterm. We will place a '1' in the cells corresponding to the binary minterms identified above, and a '0' in all other cells.

A standard layout for a 3-variable K-map (with xy as rows and z as columns) is as follows. Note the Gray code sequence for the xy rows (00, 01, 11, 10) to ensure adjacency.

K-Map Representation of F(x,y,z) = ∑(0,2,5,6)

Step no. 2:

Formulate the Boolean Expression: F = xy’+z’

Part 3.2.3 DON'T CARE CONDITIONS

Functions that have unspecified outputs for some input combination are called incompletely specified functions. In most applications, whatever value is assumed by this function is simply ignored. The unspecified minterms of such function are called don't care conditions.

"Don't care" condition is such that an output value may have the value of 'O' or '1' without affecting the desired logic operation. This condition can be used on a K-map to provide further simplification of the Boolean expression.

Example no. 4

Simplify the Boolean function

F (w, x, y, z) = 2(1, 3, 7, 11, 15) that has the don't care conditions

d (w, x, y, z) = Z(0, 2, 5)

Solution no. 4

Two possible simplified expressions can be obtained.

Solution 1.

F=w’x’+yz

Solution 2.

F=w’x’+yz